#include "help.hpp"

using namespace std;
class Solution
{
public:
    vector<vector<string>> arr;
    vector<string> ans;
    bool IsValid(vector<vector<bool>> m, int i, int j)
    {
        int n = m.size();
        int t = i, k = j;
        if (i == 0)
            return true;
        while (i > 0)
        {
            if (m[--i][j] == 1)
                return false;
        }
        i = t;
        j = k;
        while (i > 0 && j > 0)
        {
            if (m[--i][--j] == 1)
                return false;
        }
        i = t;
        j = k;
        while (i > 0 && j < n)
        {
            if (m[--i][++j] == 1)
                return false;
        }
        return true;
    }
    void bls(int k, int n, vector<vector<bool>> &m)
    {
        string s(n, '.');
        if (k == n)
        {
            arr.push_back(ans);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (IsValid(m, k, i))
            {
                s[i] = 'Q';
                m[k][i] = 1;
                ans.push_back(s);
            }
            else
                continue;
            bls(k + 1, n, m);
            s[i] = '.';
            m[k][i] = 0;
            ans.pop_back();
        }
    }
    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<bool>> m(n, vector<bool>(n, 0));
        bls(0, n, m);
        return arr;
    }
};

int main(int argc, char const *argv[])
{

    Solution s;
    auto v = s.solveNQueens(8);
    int n = v.size();
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            auto temp = v[i][j];
            std::cout << temp << " ";
        }
        cout << "\n";
    }
    return 0;
}
